package LeetCode;
import java.util.*;
public class LeetCodeMain6 {
    List<Integer> list1=new ArrayList<>();
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        list.add(new ArrayList<>());
        return list;
    }
    public void backtracking(int[] nums,int startIndex){
        list.add(new ArrayList<>(list1));

        if (list1.size()>nums.length){
            return;
        }
        for (int i = startIndex; i < nums.length; i++) {
            list1.add(nums[i]);
            backtracking(nums,i+1);
            list1.remove(list1.size()-1);
        }

    }
//    public List<String> restoreIpAddresses(String s) {
//        if (s.length()>12){
//            return list;
//        }
//        backtracking1(s,0,0);
//        return list;
//    }
//    public void backtracking1(String s,int startIndex,int pointNum){
//        if(pointNum==3){
//            if (isValid(s,startIndex,s.length()-1)){
//                list.add(s);
//            }return;
//        }
//        for (int i = startIndex; i < s.length(); i++) {
//            if (isValid(s,startIndex,i)){
//                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
//                pointNum++;
//                backtracking1(s,i+2,pointNum);
//                pointNum--;
//                s=s.substring(0,i+1)+s.substring(i + 2);
//            }else {
//                break;
//            }
//        }
//    }
    public boolean isValid(String s,int start,int end){
        if (start>end){
            return false;
        }
        char ch=s.charAt(start);
        if (ch=='0'&&start!=end){
            return false;
        }
        int sum=0;
        for (int i = start; i <=end ; i++) {
            char ch1= s.charAt(i);
            if (ch1<'0'||ch1>'9'){
                return false;
            }
            sum =sum*10+(ch1-'0');
            if (sum>=0&&sum<=255){
                return true;
            }
        }
        return false;
    }
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> list=new ArrayList<>();
        if (nums.length<3||nums==null){
            return list;
        }
        Arrays.sort(nums);
        int n= nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i]>0){
                break;
            }
            int one=nums[i];
            if (i>0&&nums[i]==nums[i-1]){
                continue;
            }
            Set<Integer> set=new HashSet<>();
            for (int j = i+1; j < n; j++) {
                int three=nums[j];
                int tow=-(three+one);
                if (set.contains(tow)){
                    list.add(new ArrayList<>(Arrays.asList(one,tow,three)));
                    while (j<n-1&&nums[j]==nums[j+1]){
                        j++;
                    }
                }
                set.add(three);
            }
        }
        return list;
    }
    public int reverse(int x) {
        int n = 0;
        while(x != 0) {
            if (n>Integer.MAX_VALUE/10||n<Integer.MIN_VALUE/10){
                return 0;
            }
            n = n*10 + x%10;
            x = x/10;
        }
        return n;
    }
    public static void main(String[] args) {
        String str=new String("PAYPALISHIRING");
        System.out.println(str.length());
    }
}
